import java.util.TreeMap;

public class Token implemenets Comparable<Token> {

  public final String value; // String representation of Token
  public final int number;   // Numeric value (usage depends on type)
  private final byte type;   // Type of token

  // Constructors are private; Use static methods to make Tokens
  private Token() { throw new Error("Do not use this constructor!"); }
  private Token(byte t, String v, int n) {
    type = t; value = v; number = n;
    if(t > T_COMMENT && (t & T_KEY_VALUE) != T_VALUE) {
      PRE_DEF_TOKENS.put(v,this);
    }
  }

  // Private values for Token.type
  private static final byte T_ERROR      = 0x00;
  private static final byte T_COMMENT    = 0x01;
  private static final byte T_FORMAT     = 0x02;
  private static final byte T_DIRECTIVE  = 0x03;
  private static final byte T_OPERATOR   = 0x10;
  private static final byte T_ASSIGN_OP  = 0x11; // assignment operators
  private static final byte T_BITWISE_OP = 0x12; // & | ^
  private static final byte T_COMPARE_OP = 0x13; // == != < >
  private static final byte T_SHIFT_OP   = 0x14; // << >> >>>
  private static final byte T_UNARY_OP   = 0x15; // + - ~ ++ -- !
  private static final byte T_KEYWORD    = 0x20;
  private static final byte T_PRIMITIVE  = 0x21; // primitive datatypes
  private static final byte T_MODIFIER   = 0x22; // static final volitale T_ACCESS_MOD
  private static final byte T_ACCESS_MOD = 0x23; // public private protected
  private static final byte T_VALUE      = 0x40; // Tokens that may act as values
  private static final byte T_IDENTIFIER = 0x41;
  private static final byte T_STRING_LIT = 0x42;
  private static final byte T_CHAR_LIT   = 0x43;
  private static final byte T_NUMBER     = 0x44;
  private static final byte T_BIN_NUMBER = 0x45;
  private static final byte T_DEC_NUMBER = 0x46;
  private static final byte T_HEX_NUMBER = 0x47;
  private static final byte T_KEY_VALUE  = T_KEYWORD | T_VALUE;
  private boolean typeIsIn(byte mask) { return (type & mask) == mask; }
 
  // Keep a SINGLE entry for each token
  private static final TreeMap<String,Token> USER_DEF_TOKENS = new TreeMap<String,Token>();
  private static final TreeMap<String,Token> PRE_DEF_TOKENS = new TreeMap<String,Token>();
 
  // For use with formatting strings:
  private static final String CTRL_CHARS = "\b\n\r\t\0\\\'\"";
  private static final String ESC_CHARS = "bnrt0\\\'\"";
  private static final String DOUBLE_OPS = "&|=+-><";
  private static final String EQ_OPS = "<>!+-*%/&|^";

  // Predefined Tokens (grouped by type)
  public static final Token DIR_END         = new Token(T_DIRECTIVE, "#end",        0);
  public static final Token DIR_FOR         = new Token(T_DIRECTIVE, "#for",        0);
  public static final Token DIR_INCLUDE     = new Token(T_DIRECTIVE, "#include",    0);
  public static final Token DIR_ASSEMBLY    = new Token(T_DIRECTIVE, "#assembly",   0);
  public static final Token DIR_ALLOCATE    = new Token(T_DIRECTIVE, "#allocate",   0);
  public static final Token DIR_ENVIRONMENT = new Token(T_DIRECTIVE, "#environment",0);
  public static final Token ERR_BAD_CHAR     = new Token(T_ERROR, "malformed character literal",0);
  public static final Token ERR_OPEN_CHAR    = new Token(T_ERROR, "unclosed character literal", 0);
  public static final Token ERR_BAD_NUMBER   = new Token(T_ERROR, "malformed numeric value",    0);
  public static final Token ERR_OPEN_STRING  = new Token(T_ERROR, "unclosed string literal",    0);
  public static final Token ERR_BAD_ESC_CHAR = new Token(T_ERROR, "invalid escape character",   0);
  public static final Token EOF       = new Token(T_FORMAT, "END_OF_FILE", 0);
  public static final Token NEW_FILE  = new Token(T_FORMAT, "NEW_FILE",    0);
  public static final Token NEW_LINE  = new Token(T_FORMAT, "NEW_LINE",    0);
  public static final Token AND       = new Token(T_OPERATOR, "&&",0);
  public static final Token ARROW     = new Token(T_OPERATOR, "=>",0);
  public static final Token AT        = new Token(T_OPERATOR, "@", 0);
  public static final Token COLON     = new Token(T_OPERATOR, ":", 0);
  public static final Token COMMA     = new Token(T_OPERATOR, ",", 0);
  public static final Token DOT       = new Token(T_OPERATOR, ".", 0);
  public static final Token L_BRACE   = new Token(T_OPERATOR, "{", 0);
  public static final Token L_BRACKET = new Token(T_OPERATOR, "[", 3);
  public static final Token L_PAREN   = new Token(T_OPERATOR, "(", 0);
  public static final Token MOD       = new Token(T_OPERATOR, "%", 0);
  public static final Token OR        = new Token(T_OPERATOR, "||",0);
  public static final Token QUESTION  = new Token(T_OPERATOR, "?", 0);
  public static final Token R_BRACE   = new Token(T_OPERATOR, "}", 0);
  public static final Token R_BRACKET = new Token(T_OPERATOR, "]", 0);
  public static final Token R_PAREN   = new Token(T_OPERATOR, ")", 0);
  public static final Token SEMI      = new Token(T_OPERATOR, ";", 0);
  public static final Token SLASH     = new Token(T_OPERATOR, "/", 0);
  public static final Token STAR      = new Token(T_OPERATOR, "*", 0);
  public static final Token AND_EQ    = new Token(T_ASSIGN_OP, "&=",  0);
  public static final Token ASSIGN    = new Token(T_ASSIGN_OP, "=",   0);
  public static final Token DIV_EQ    = new Token(T_ASSIGN_OP, "/=",  0);
  public static final Token L_EQ      = new Token(T_ASSIGN_OP, "<<=", 0);
  public static final Token MINUS_EQ  = new Token(T_ASSIGN_OP, "-=",  0);
  public static final Token MOD_EQ    = new Token(T_ASSIGN_OP, "%=",  0);
  public static final Token OR_EQ     = new Token(T_ASSIGN_OP, "|=",  0);
  public static final Token PLUS_EQ   = new Token(T_ASSIGN_OP, "+=",  0);
  public static final Token R_EQ      = new Token(T_ASSIGN_OP, ">>=", 0);
  public static final Token RR_EQ     = new Token(T_ASSIGN_OP, ">>>=",0);
  public static final Token TIMES_EQ  = new Token(T_ASSIGN_OP, "*=",  0);
  public static final Token XOR_EQ    = new Token(T_ASSIGN_OP, "^=",  0);
  public static final Token AMP       = new Token(T_BITWISE_OP, "&", 0);
  public static final Token BAR       = new Token(T_BITWISE_OP, "|", 0);
  public static final Token XOR       = new Token(T_BITWISE_OP, "^", 0);
  public static final Token EQ_TO     = new Token(T_COMPARE_OP, "==",0);
  public static final Token GREATER   = new Token(T_COMPARE_OP, ">", 0);
  public static final Token GREATER_EQ= new Token(T_ASSIGN_OP, ">=", 0);
  public static final Token LESS      = new Token(T_COMPARE_OP, "<", 0);
  public static final Token LESS_EQ   = new Token(T_ASSIGN_OP, "<=", 0);
  public static final Token NOT_EQ    = new Token(T_COMPARE_OP, "!=",0);
  public static final Token L_SHIFT   = new Token(T_SHIFT_OP, "<<", 0);
  public static final Token R_SHIFT   = new Token(T_SHIFT_OP, ">>", 0);
  public static final Token RR_SHIFT  = new Token(T_SHIFT_OP, ">>>",0);
  public static final Token MINUS     = new Token(T_UNARY_OP, "-", 0);
  public static final Token PLUS      = new Token(T_UNARY_OP, "+", 0);
  public static final Token COMPL     = new Token(T_UNARY_OP, "~", 0);
  public static final Token INC       = new Token(T_UNARY_OP, "++",1);
  public static final Token DEC       = new Token(T_UNARY_OP, "--",1);
  public static final Token NOT       = new Token(T_UNARY_OP, "!", 0);
  public static final Token ABSTRACT  = new Token(T_KEYWORD, "abstract", 2);
  public static final Token ASSEMBLY  = new Token(T_KEYWORD, "assembly", 1);
  public static final Token BREAK     = new Token(T_KEYWORD, "break",    1);
  public static final Token CASE      = new Token(T_KEYWORD, "case",     1);
  public static final Token CLASS     = new Token(T_KEYWORD, "class",    2);
  public static final Token CONTINUE  = new Token(T_KEYWORD, "continue", 1);
  public static final Token DEFAULT   = new Token(T_KEYWORD, "default",  1);
  public static final Token DELETE    = new Token(T_KEYWORD, "delete",   1);
  public static final Token DO        = new Token(T_KEYWORD, "do",       1);
  public static final Token ELSE      = new Token(T_KEYWORD, "else",     1);
  public static final Token FOR       = new Token(T_KEYWORD, "for",      1);
  public static final Token IF        = new Token(T_KEYWORD, "if",       1);
  public static final Token IS        = new Token(T_KEYWORD, "is",       0);
  public static final Token NAMESPACE = new Token(T_KEYWORD, "namespace",2);
  public static final Token NEW       = new Token(T_KEYWORD, "new",      1);
  public static final Token OUT       = new Token(T_KEYWORD, "out",      0);
  public static final Token REF       = new Token(T_KEYWORD, "ref",      0);
  public static final Token RETURN    = new Token(T_KEYWORD, "return",   1);
  public static final Token SIZEOF    = new Token(T_KEYWORD, "sizeof",   0);
  public static final Token SWITCH    = new Token(T_KEYWORD, "switch",   1);
  public static final Token UNTIL     = new Token(T_KEYWORD, "until",    1);
  public static final Token USING     = new Token(T_KEYWORD, "using",    2);
  public static final Token VIRTUAL   = new Token(T_KEYWORD, "virtual",  2);
  public static final Token WHILE     = new Token(T_KEYWORD, "while",    1);
  public static final Token YIELD     = new Token(T_KEYWORD, "yield",    1);
  public static final Token BYTE      = new Token(T_PRIMITIVE, "byte", 3);
  public static final Token WORD      = new Token(T_PRIMITIVE, "word", 3);
  public static final Token CHAR      = new Token(T_PRIMITIVE, "char", 3);
  public static final Token BOOL      = new Token(T_PRIMITIVE, "bool", 3);
  public static final Token VOID      = new Token(T_PRIMITIVE, "void", 3);
  public static final Token UBYTE     = new Token(T_PRIMITIVE, "ubyte",3);
  public static final Token UWORD     = new Token(T_PRIMITIVE, "uword",3);
  public static final Token FINAL     = new Token(T_MODIFIER, "final",   3);
  public static final Token STATIC    = new Token(T_MODIFIER, "static",  3);
  public static final Token VOLITALE  = new Token(T_MODIFIER, "volitale",3);
  public static final Token PRIVATE   = new Token(T_ACCESS_MOD, "private",  2);
  public static final Token PROTECTED = new Token(T_ACCESS_MOD, "protected",2);
  public static final Token PUBLIC    = new Token(T_ACCESS_MOD, "public",   2);
  public static final Token BASE      = new Token(T_KEY_VALUE, "base", 1);
  public static final Token FALSE     = new Token(T_KEY_VALUE, "false",0);
  public static final Token NULL      = new Token(T_KEY_VALUE, "null", 0);
  public static final Token THIS      = new Token(T_KEY_VALUE, "this", 1);
  public static final Token TRUE      = new Token(T_KEY_VALUE, "true", 0);
 
  // Instance methods
  public String toString() { return value; }
  public boolean isAccessMod( ) { return type == T_ACCESS_MOD; }
  public boolean isAssignment() { return type == T_ASSIGN_OP;  }
  public boolean isBinNum(    ) { return type == T_BIN_NUMBER; }
  public boolean isBitwiseOp( ) { return type == T_BITWISE_OP; }
  public boolean isChar(      ) { return type == T_CHAR_LIT;   }
  public boolean isComparison() { return type == T_COMPARE_OP; }
  public boolean isDecNum(    ) { return type == T_DEC_NUMBER; }
  public boolean isDirective( ) { return type == T_DIRECTIVE;  }
  public boolean isError(     ) { return type == T_ERROR;      }
  public boolean isFormat(    ) { return type == T_FORMAT;     }
  public boolean isHexNum(    ) { return type == T_HEX_NUMBER; }
  public boolean isIdent(     ) { return type == T_IDENTIFIER; }
  public boolean isKeyword(   ) { return typeIsIn(T_KEYWORD);  }
  public boolean isModifier(  ) { return typeIsIn(T_MODIFIER); }
  public boolean isNumber(    ) { return typeIsIn(T_NUMBER);   }
  public boolean isOperator(  ) { return typeIsIn(T_OPERATOR); }
  public boolean isPrimitive( ) { return type == T_PRIMITIVE;  }
  public boolean isShiftOp(   ) { return type == T_SHIFT_OP;   }
  public boolean isString(    ) { return type == T_STRING_LIT; }
  public boolean isUnaryOp(   ) { return type == T_UNARY_OP;   }
  public boolean isValue(     ) { return typeIsIn(T_VALUE);    }
  public boolean isInnerStarting() { return (type != T_NUMBER) && ((number & 0x01) == 1); }
  public boolean isOuterStarting() { return (type != T_NUMBER) && ((number & 0x02) == 2); }
  public int compareTo(Token t) {
    if(this == t) return 0; // This will be the most common "==" case.
    return (type == t.type)?
      ((number == t.number)? value.compareTo(t.value) : ((number < t.number)? -1 : 1)) :
      ((type < t.type)? -1 : 1));
  }
  public boolean equals(Object o) {
    return this == o || (o instanceof Token &&
      ((Token)o).type == type && ((Token)o).number == number);
  } // Use == for non-number tokens (common references are then gauranteed).

  // Static Token making methods
  public static Token makeIdent(String ident) { return getUserToken(T_IDENTIFIER, ident, 3); }
  public static Token makeComment(String comment) { return getUserToken(T_COMMENT, comment, 0); }
  public static Token makeChar(char ch) throws Exception { return makeChar(Character.toString(ch)); }
  public static Token makeBinNum(int num) { return new Token(T_BIN_NUMBER, "0b"+Integer.toString(num,2), num);  }
  public static Token makeHexNum(int num) { return new Token(T_HEX_NUMBER, "0x"+Integer.toString(num,16), num); }
  public static Token makeNumber(int num) { return new Token(T_DEC_NUMBER, Integer.toString(num), num);         }

  public static Token makeNumber(String num) {
    if(num.length() > 1 && num.charAt(0) == '0') {
      char ch = num.charAt(1);
      if(ch == 'x' || ch == 'h') { return new Token(T_HEX_NUMBER, num, Integer.parseInt(num.substring(2), 16)); }
      if(ch == 'b') { return new Token(T_BIN_NUMBER, num, Integer.parseInt(num.substring(2), 2)); }
      if(ch == 'd') { return new Token(T_DEC_NUMBER, num, Integer.parseInt(num.substring(2))); }
    }
    return new Token(T_DEC_NUMBER, num, Integer.parseInt(num));
  }

  public static Token makeChar(String ch) throws Exception {
    if(!isValidChar(ch))
      throw new Exception("Invalid character format: \'"+ch+'\'');
    char n = ch.charAt(0);
    if(n == '\\') { n = CTRL_CHARS.charAt(ESC_CHARS.indexOf(ch.charAt(1))); }
    return getUserToken(T_CHAR_LIT, "\'"+ch+'\'', n);
  }

  public static Token makeString(String str) throws Exception {
    if(!isValidString(str))
      throw new Exception("Invalid string format: \""+str+'\"');
    return getUserToken(T_STRING_LIT, "\""+str+'\"', 0);
  }

  // Static Token parsing methods
 
  public static boolean isIdentChar(char ch) {
    return Character.isLetterOrDigit(ch) || ch == '_';
  }

  public static Token parseNext(StringBuilder source) {
    int idx, len = source.length();

    // Remove whitespace
    for(idx = 0; idx < len && Character.isWhitespace(source.charAt(idx)); idx++) {
      char ch = source.charAt(idx);
      if(ch == '\r' || ch == '\n') {
        source.delete(0,idx+1);
        return NEW_LINE;
      }
    }
   
    // Remove comments
    if(idx < len-1 && source.charAt(idx) == '/') {
      if(source.charAt(idx+1) == '/') {
        int i = idx+2;
        char ch = source.charAt(i++);
        while(i < len && ch != '\r' && ch != '\n') {
          ch = source.charAt(i++);
        }
        String value = source.substring(idx,i);
        source.delete(idx,i);
        return makeComment(value);
      }
      if(source.charAt(idx+1) == '*') {
        int i = idx+2;
        char last = 0, ch = source.charAt(i++);
        while(i < len && (last != '*' || ch != '/')) {
          last = ch; ch = source.charAt(i++);
        }
        String value = source.substring(idx,i);
        source.delete(idx,i);
        return makeComment(value);
      }
    }
   
    // Signal EOF
    if(idx >= len) {
      source.delete(0,idx);
      return EOF;
    }
   
    int begin = idx;
    char start = source.charAt(idx);
    boolean directive = (start == '#');
    if(directive) { idx++; start = source.charAt(idx); }

    // Handle keywords and directives
    if(isIdentChar(start) || directive) {
      while(idx < len && isIdentChar(source.charAt(idx))) { idx++; }
      String value = source.substring(begin, idx);
      source.delete(0,idx);
      Token t = PRE_DEF_TOKENS.get(value);
      if(t != null) { return t; }
      if(directive) { return new Token(T_ERROR, "Unrecognized directive: #"+value, 0); }
      if(Character.isDigit(value.charAt(0))) { return makeNumber(value); }
      return makeIdent(value);
    }

    // Handle string and character literals
    if(start == '\"' || start == '\'') {
      while(++idx < len) {
        char ch = source.charAt(idx);
        if(ch == '\\') { idx++; continue; }
        if(ch == '\r' || ch == '\n') { break; }
        if(ch == start) {
          String value = source.substring(begin+1, idx);
          source.delete(0, idx+1);
          try { return ((start == '\"')? makeString(value) : makeChar(value)); }
          catch(Exception e) { return new Token(T_ERROR, e.getMessage(), 0); }
        }
      }
      String value = source.substring(begin, idx-1);
      source.delete(0,idx);
      return new Token(T_ERROR, "Missing closing quote on literal: "+start+value, 0);
    }

    // Handle operators
    char next = (idx < len-1)? source.charAt(idx+1) : 0;
    if(start == next && DOUBLE_OPS.indexOf(start) >= 0) {
      if(idx++ < len-2 && start == '>' && source.charAt(idx+1) == '>') { idx++; }
      if((start == '>' || start == '<') && source.charAt(idx+1) == '=') { idx++; }
    }
    else if((next == '=' && EQ_OPS.indexOf(start) >= 0) || (start == '=' && next == '>')) {
      idx++;
    }
   
    String value = source.substring(begin, idx+1);
    source.delete(0,idx+1);
    Token t = PRE_DEF_TOKENS.get(value);
    if(t != null) { return t; }
    return new Token(T_ERROR, "Unexpected symbol found ("+value+")", 0);
  }
 
  public static void tokenize(String source, java.util.List<Token> tokens) {
    StringBuilder sb = new StringBuilder(source); Token t = null;
    while(sb.length() > 0) { t = parseNext(sb); tokens.add(t); }
    if(token != EOF) { tokens.add(EOF); }
  }
 
  private static boolean isValidString(String str) {
    boolean last = false;
    for(int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i);
      if(last && ESC_CHARS.indexOf(ch) < 0) { return false; }
      if(Character.isWhitespace(ch) && ch != ' ' && ch != '\t') { return false; }
      last = (!last && ch == '\\');
    }
    return !last;
  }
 
  private static boolean isValidChar(String str) {
    int len = str.length();
    if(len < 1) { return false; }
    char ch = str.charAt(0);
    if(ch == '\\') { return (len == 2 && ESC_CHARS.indexOf(str.charAt(1)) >= 0); }
    return (len == 1 && (!Character.isWhitespace(ch) || ch == '\t' || ch == ' '));
  }
 
  private static Token getUserToken(byte type, String value, int number) {
    Token t = USER_DEF_TOKENS.get(value);
    if(t == null) {
      t = new Token(type, value, number);
      USER_DEF_TOKENS.put(value,t);
    } return t;
  }

  // THIS METHOD IS FOR TESTING PURPOSES ONLY:
  public static void main(String[] args) {
    javax.swing.JTextArea jta = new javax.swing.JTextArea();
    try { jta.read(new java.io.BufferedReader(new java.io.FileReader("Token.java")), null); }
    catch(Throwable t) { System.out.println("OOPS!\n"+t.getMessage()); }
    StringBuilder source = new StringBuilder(jta.getText());
    int indent = 0;
    while(source.length() > 0) {
      Token t = parseNext(source);
      if(t == L_BRACE) { indent++; }
      else if(t == R_BRACE) { indent--; }
      if(t == NEW_LINE) {
        System.out.println();
        for(int i=0; i<indent; i++) { System.out.print("   "); }
      }
      else { System.out.print(t.toString()+' '); }
    }
  }
}